package com.javabasic.algorithm.leetcode;

import java.util.HashMap;

/**
 * @Author xiongmin
 * @Description //TODO
 * @Date 2019/12/10 19:46
 * @Version 1.0
 * 题解：https://leetcode-cn.com/problems/split-array-into-consecutive-subsequences/solution/fen-ge-shu-zu-wei-lian-xu-zi-xu-lie-by-leetcode/
 **/
public class SplitArrayintoConsecutiveSubsequences {

    /**
     * 具有限定策略的贪心算法
     * 贪心策略：就是使序列尽可能的长
     * @param nums
     * @return
     */
    public boolean isPossible(int[] nums) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num,map.getOrDefault(num,0) + 1);
        }

        for (int num : nums) {
            int cur = num;
            int subNum = 0;
            int temp = 1;
            // 限定策略：后面元素的数量要大于或等于前面元素的数量才可以加入到序列中
            while (map.getOrDefault(cur,0) >= temp) {
                temp = map.getOrDefault(cur,0);
                map.put(cur,temp-1);
                cur++;
                subNum++;
            }
            if (subNum < 3 && subNum > 0) {
                return false;
            }
        }
        return true;
    }
}
